package 打牢基础30天.day04.my;

/**
 * @Author yaya
 * @Create 2024/6/14 15:06
 * Description: 将单向链表按某值划分成左边小、中间相等、右边大的形式
 */
public class Code05_SmallerEqualBigger {
    public static class Node {
        public int value;
        public Node next;

        Node(int data) {
            this.value = data;
        }
    }

    /**
     * 使用荷兰国旗问题中的partition；
     * 时间：n 空间：n  使用了额外的数组存储head每个节点
     *
     * @param head
     */
    public static Node listPartition1(Node head, int pivot) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        // 1、先将node转换成arr
        // 计算数组需要多大
        int i = 0;
        Node temp = head;
        while (temp != null) {
            i++;
            temp = temp.next;
        }

        Node[] nodeArr = new Node[i];
        temp = head;
        for (int j = 0; j != nodeArr.length; j++) {
            nodeArr[j] = temp;
            temp = temp.next;
        }

        // 2、使用荷兰国旗中的partition方法，按照需求排序
        partition1(nodeArr, pivot);

        // 3、将arr转回node节点，并相连
        for (i = 1; i < nodeArr.length; i++) {
            nodeArr[i - 1].next = nodeArr[i];
        }
        nodeArr[i - 1].next = null;
        return nodeArr[0];
    }

    private static void partition1(Node[] nodeArr, int pivot) {
        int small = -1;
        int big = nodeArr.length;
        int index = 0;

        while (index < big) {
            if (nodeArr[index].value < pivot) {
                swap(nodeArr, ++small, index++);
            } else if (nodeArr[index].value > pivot) {
                swap(nodeArr, --big, index);
            } else {
                index++;
            }
        }
    }

    private static void swap(Node[] nodeArr, int n1, int n2) {
        Node temp = nodeArr[n1];
        nodeArr[n1] = nodeArr[n2];
        nodeArr[n2] = temp;
    }

    /**
     * 不使用额外空间，将空间分为3块，分别使用头尾指针表示，最后连接起来就是完整链表
     *
     * @param head
     * @param pivot
     */
    public static Node listPartition2(Node head, int pivot) {
        // 分别为小中大三块空间的头尾指针，h:head t:tail， temp临时变量
        Node sh = null, st = null;
        Node eh = null, et = null;
        Node bh = null, bt = null;
        Node temp = null;
        // 放在对应区域中
        while (head != null) {
            temp = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (sh == null) {
                    sh = head;
                    st = head;
                } else {
                    st.next = head;
                    st = head;
                }
            } else if (head.value == pivot) {
                if (eh == null) {
                    eh = head;
                    et = head;
                } else {
                    et.next = head;
                    et = head;
                }
            } else {
                if (bh == null) {
                    bh = head;
                    bt = head;
                } else {
                    bt.next = head;
                    bt = head;
                }
            }
            head = temp;
        }

        if (sh != null) {
            st.next = eh;
            et = et == null ? st : et;
        }
        if (et != null) {
            et.next = bh;
        }

        return (sh != null) ? sh : (eh != null) ? eh : bh;

    }

    public static Node listPartition3(Node head, int pivot) {
        Node sh = null;
        Node st = null;
        Node eh = null;
        Node et = null;
        Node bh = null;
        Node bt = null;
        Node next = null;

        while (head != null) {
            next = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (sh == null) {
                    sh = head;
                    st = head;
                } else {
                    st.next = head;
                    st = head;
                }
            } else if (head.value == pivot) {
                if (eh == null) {
                    eh = head;
                    et = head;
                } else {
                    et.next = head;
                    et = head;
                }
            } else {
                if (bh == null) {
                    bh = head;
                    bt = head;
                } else {
                    bt.next = head;
                    bt = head;
                }
            }
            head = next;
        }

        // 拼接node
        if (sh != null){
            st.next = eh;
            et = et == null ? st : et;
        }
        if (et != null){
            et.next = bh;
        }

        return sh != null ? sh : eh != null? eh : bh;
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }


    public static void main(String[] args) {
        Node head1 = new Node(7);
        head1.next = new Node(9);
        head1.next.next = new Node(1);
        head1.next.next.next = new Node(8);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(2);
        head1.next.next.next.next.next.next = new Node(5);
        printLinkedList(head1);
        // head1 = listPartition1(head1, 4);
        head1 = listPartition3(head1, 5);
        printLinkedList(head1);

    }
}
